from typing import List, Literal, Optional, Tuple

# import numpy as np
# from chernc.textdiff.fuzz_myers import Insert, Keep, Remove, fuzz_myers_diff, code_line_equal, remove_comments
from chernc.textdiff.myers import Insert, Keep, Remove, myers_diff, diff_to_string
from chernc.textdiff.fuzz_myers import code_line_equal, remove_comments

def get_balanced_stack(s: str) -> List[str]:
    s = remove_comments(s)
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    in_quotes = False
    quote_char = None

    for i, char in enumerate(s):
        # print(char)
        # print(stack)
        if char in "'\"" and (i == 0 or s[i-1] != '\\'):
            if in_quotes and char == quote_char:
                in_quotes = False
                quote_char = None
            elif not in_quotes:
                in_quotes = True
                quote_char = char
        if in_quotes:
            continue

        if char in mapping.values():
            stack.append(char)
        elif char in mapping.keys():
            if len(stack) > 0:
                if stack[-1] != mapping[char]:
                    return stack
                else:
                    stack.append(char)
                    if len(stack) >= 2:
                        stack.pop()
                        stack.pop()
                    else:
                        return stack
            else:
                stack.append(char)
                return stack
            
    return stack

def get_balanced_direction(s: str) -> Optional[Literal["forward", "back"]]:
    stack = get_balanced_stack(s)
    # print(stack)
    if len(stack) == 0:
        return None
    else:
        top = stack[-1]
        if top in ["[", "(", "{"]:
            return "back"
        elif top in ["]", ")", "}"]:
            return "forward"
        return None

def is_balanced(s: str) -> bool:
    return len(get_balanced_stack(s)) == 0

def replace_fix_result_in_input(text: str, replacement: str, start_line: int, end_line: int):
    """
    小工具： 把text中start_line到end_line替换为replacement
    假设 line_diff_match 函数返回匹配的行范围：start_line 和 end_line

    :param text: _description_
    :type text: _type_
    :param replacement: _description_
    :type replacement: _type_
    :param start_line: _description_
    :type start_line: _type_
    :param end_line: _description_
    :type end_line: _type_
    :return: _description_
    :rtype: _type_
    """
    # 将输入文本 to_fix 按行分割
    rhs_lines = text.splitlines()

    # 将修复结果按行分割
    lhs_lines = replacement.splitlines()

    # 在 to_fix 中的相应位置替换掉指定范围的行
    # 先保留修复前的部分，再插入修复后的部分，最后加上修复后的尾部
    new_lines = rhs_lines[:start_line] + lhs_lines + rhs_lines[end_line:]

    # 重新组合成字符串
    return "\n".join(new_lines)

def replace_fix_result_in_input_debug(text: str, replacement: str, start_line: int, end_line: int):
    # 将输入文本 to_fix 按行分割
    rhs_lines = text.splitlines()

    # 将修复结果按行分割
    lhs_lines = replacement.splitlines()

    # 在 to_fix 中的相应位置替换掉指定范围的行
    # 先保留修复前的部分，再插入修复后的部分，最后加上修复后的尾部
    new_lines = rhs_lines[:start_line] + \
        diff_to_string(myers_diff(rhs_lines[start_line:end_line], lhs_lines), line_number=False).splitlines() + \
        rhs_lines[end_line:]

    # 重新组合成字符串
    return "\n".join(new_lines)

def get_first_nonempty_line(lines: List[str]) -> int:
    first_nonempty_line = 0
    while first_nonempty_line < len(lines):
        if lines[first_nonempty_line].strip() != "":
            break
        first_nonempty_line += 1
    return first_nonempty_line


def get_last_nonempty_line(lines: List[str]) -> int:
    last_nonempty_line = len(lines) - 1
    while last_nonempty_line >= 0:
        if lines[last_nonempty_line].strip() != "":
            break
        last_nonempty_line -= 1
    return last_nonempty_line


def line_diff_match(before_lines: List[str], after_lines: List[str], range_start: int, range_end: int) -> Tuple[int, int]:
    """行号end不包括结尾行

    :param lines: _description_
    :type lines: List[str]
    :param range_start: _description_
    :type range_start: int
    :param range_end: _description_
    :type range_end: int
    :return: _description_
    :rtype: Tuple[int, int]
    """
    # Remove Comments
    # before_lines = [remove_comments(line) for line in before_lines]
    # after_lines = [remove_comments(line) for line in after_lines]

    diff_results = myers_diff(before_lines, after_lines)
    # before delete and after insert
    before_lines_delete = []
    after_lines_insert = []
    line_before = 0
    line_after = 0
    for elem in diff_results:
        if isinstance(elem, Keep):
            line_after += 1
            line_before += 1
        elif isinstance(elem, Insert):
            after_lines_insert.append(line_after)
            line_after += 1
        elif isinstance(elem, Remove):
            before_lines_delete.append(line_before)
            line_before += 1
        else:
            raise Exception("unknown diff result")

    # before delete and after insert mapping
    move_mapping = {}
    after_insert_used = set()
    # 计算行号
    line_before = 0
    line_after = 0
    last_removed_line = None
    for elem in diff_results:
        if line_before < len(before_lines):
            if isinstance(elem, Keep):
                move_mapping[line_after] = line_before
                after_insert_used.add(line_after)
            elif isinstance(elem, Insert):
                if last_removed_line is not None and code_line_equal(before_lines[last_removed_line], after_lines[line_after]):
                    move_mapping[line_after] = last_removed_line
                    after_insert_used.add(line_after)
                    last_removed_line = None
            elif isinstance(elem, Remove):
                last_removed_line = line_before
        # update line number
        if isinstance(elem, Keep):
            line_after += 1
            line_before += 1
        elif isinstance(elem, Insert):
            line_after += 1
        elif isinstance(elem, Remove):
            line_before += 1
        else:
            raise Exception("unknown diff result")
    # 移动识别
    for before_delete in before_lines_delete:
        for after_insert in after_lines_insert:
            if after_insert in after_insert_used:
                continue
            if code_line_equal(before_lines[before_delete], after_lines[after_insert]):
                move_mapping[after_insert] = before_delete
                after_insert_used.add(after_insert)
                break

    # reversed_mapping = {value: key for key, value in move_mapping.items()}
    # 开始匹配
    result_start = None
    result_end = None
    candidates: List[Tuple[Tuple[int, int], Tuple[float, int]]] = []

    for start_pos in range(0, len(after_lines)):
        if start_pos not in move_mapping:
            continue
        for end_pos in range(start_pos + 1, len(after_lines) + 1):
            if end_pos - 1 not in move_mapping:
                continue
            matched_line = 0
            outside_matched_line = 0
            for line in range(0, len(after_lines)):
                if line >= start_pos and line < end_pos:
                    if line not in move_mapping:
                        outside_matched_line -= 1
                        continue
                    if move_mapping[line] >= range_start and move_mapping[line] < range_end:
                        matched_line += 1
                else:
                    if line not in move_mapping:
                        continue
                    if move_mapping[line] < range_start or move_mapping[line] >= range_end:
                        outside_matched_line += 1
                    else:
                        outside_matched_line -= 1
            line_num = end_pos - start_pos
            matched_percentage = matched_line / line_num
            # merge candidates
            candidates_to_remove = []
            for candidate_i, candidate in enumerate(candidates):
                if candidate[0][0] >= start_pos and candidate[0][1] <= end_pos:
                    candidates_to_remove.append(candidate_i)
            for candidate_i in candidates_to_remove:
                candidates.pop(candidate_i)
            candidates.append(((start_pos, end_pos), (matched_line + outside_matched_line, line_num)))

    candidates = sorted(candidates, key=lambda x: x[1], reverse=True)
    # print(candidates)
    if len(candidates) == 0:
        result_start = 0
        result_end = 0
    else:
        matched_ele = candidates[0]
        result_start = matched_ele[0][0]
        result_end = matched_ele[0][1]
    # 后处理
    if result_start is None:
        result_start = 0
    if result_end is None:
        result_end = 0
    if result_start < 0:
        result_start = 0
    if result_start > len(after_lines):
        result_start = len(after_lines)
    if result_end < 0:
        result_end = 0
    if result_end > len(after_lines):
        result_end = len(after_lines)
    
    # 保证括号成对匹配
    if is_balanced("\n".join(before_lines[range_start:range_end])):
        direction = get_balanced_direction("\n".join(after_lines[result_start:result_end]))
        # print(direction)
        if direction == "back":
            while result_end < len(after_lines):
                if is_balanced("\n".join(after_lines[result_start:result_end])):
                    break
                result_end += 1
        elif direction == "forward":
            while result_start > 0:
                if is_balanced("\n".join(after_lines[result_start:result_end])):
                    break
                result_start -= 1

    return result_start, result_end


def show_result(lhs_lines, rhs_lines, start_line, end_line):
    match_out = line_diff_match(lhs_lines, rhs_lines, start_line, end_line)
    print(match_out)
    print("======ORIGIN======")
    print("\n".join(lhs_lines[start_line:end_line]))

    print("======MATCHED=======")
    print("\n".join(rhs_lines[match_out[0] : match_out[1]]))

    print("=======DIFF=======")
    diff = myers_diff(lhs_lines, rhs_lines)
    for elem in diff:
        if isinstance(elem, Keep):
            print(" " + elem.line)
        elif isinstance(elem, Insert):
            print("+" + elem.line)
        else:
            print("-" + elem.line)


if __name__ == "__main__":
    print(is_balanced("[]()\"[\""))
    print(get_balanced_direction("""
        run_test(*test); // Dereference the borrow
    }
}
// CHERNC_END_MARK: /data/wangjun/github/Chern-C/examples/smallprimary/framework.c:55
"""))
    
    print(get_balanced_direction("""
    fn test(a: int, b:int) {
        int a = (
            1,
            2
"""))